package main

import "fmt"

/*
	寻找重复数
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间（包括 1 和 n）
可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数

示例 1：
输入：nums = [1,3,4,2,2]
输出：2

示例 2：
输入：nums = [3,1,3,4,2]
输出：3
 */

// 方法一 使用额外的空间 即map
func findDuplicate1(nums []int) int {
	tempMap := make(map[int]int, 0)
	for _, v := range nums {
		if _ ,ok := tempMap[v]; ok {
			tempMap[v] += 1
		}else {
			tempMap[v] = 1
		}
	}
	for i, v := range tempMap {
		if v > 1 {
			return i
		}
	}
	return 0
}


// 方法二  转换为求环的入环口
func findDuplicate(nums []int) int {
	slow, fast := 0, 0
	for {
		slow = nums[slow]
		fast = nums[nums[fast]]

		if slow == fast {
			fast = 0
			for {
				if slow == fast {
					return slow
				}
				slow = nums[slow]
				fast = nums[fast]
			}
		}
	}
}

func main()  {
	fmt.Println(findDuplicate([]int{1,3,4,2,2}))
}


